package hw04.grammar;


import java.lang.reflect.Constructor;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * The grammar is represented with Java constructs.
 * Class constructors represent productions.
 * Objects represent nonterminals.
 * Regex represents terminals.
 * 
 * 
 * @author jbelanger
 *
 * @param <E>
 */
public abstract class Grammar<E> {
	
	/**
	 * Parses a grammar from the bottom up using shift and reduce
	 * 
	 * @param input
	 * @return result
	 */
	@SuppressWarnings("unchecked")
	public E parse(String input) {
		Stack<Object> stack = new Stack<Object>();
		
		while(input.length() > 0) {
			
			//shift once
			boolean shifted = false;
			for(String terminalRegex : getTerminals().keySet()) {
				String regex = "^\\s*" + terminalRegex + "\\s*";
				Matcher m = Pattern.compile(regex).matcher(input);
				if(m.find()) {
					try {
						Class<? extends Terminal> type = getTerminals().get(terminalRegex);
						String match = m.group().trim();
						Constructor<? extends Terminal> constructor = type.getConstructor(String.class);
						Terminal t = constructor.newInstance(match);
						input = input.substring(m.end());
						stack.push(t);
						shifted = true;
						break;
					} catch(Exception e) {}
				}
			}
			if(!shifted) {
				return null;
			}
			
			//continually reduce
			boolean reduced;
			do {
				reduced = false;
				for(Class<?> nonTerminal : getProductions()) {
					for(Constructor<?> production : nonTerminal.getConstructors()) {
						Class<?>[] productionRHS = production.getParameterTypes();
						
						if(stack.size() >= productionRHS.length) {
							//test if top of stack matches production types
							Object[] stackTop = new Object[productionRHS.length];
							for(int i = stackTop.length - 1; i >= 0; i--) {
								stackTop[i] = stack.pop();
							}
							
							boolean typesMatch = true;
							for(int i = 0; i < productionRHS.length; i++) {
								if(!productionRHS[i].isAssignableFrom(stackTop[i].getClass())) {
									typesMatch = false;
									break;
								}
							}
							if(typesMatch) {
								try {
									Object obj = production.newInstance(stackTop);
									stack.push(obj);
									reduced = true;
									break;
								} catch(Exception e) {}
							}
							
							//restore stack because of failed attempt
							for(int i = 0; i < stackTop.length; i++) {
								stack.push(stackTop[i]);
							}
						}
						
					}
					if(reduced) {
						break;
					}
				}
			} while(reduced);
		}
		
		if(stack.size() == 1 && stack.peek() instanceof Executable) {
			return (E)stack.peek();
		}
		return null;
	}

	/**
	 * The matching string is passed to the corresponding Terminal object's String constructor.
	 */
	public abstract Map<String, Class<? extends Terminal>> getTerminals();

	/**
	 * Productions in the form <A> := <A> <B> | <B> is represented as:
	 * 
	 * class A {
	 * 		public A(A arg1, B arg2) {}
	 * 		public A(B arg1) {}
	 * }
	 * 
	 * When sequence of nonterminals match one of A's constructor's signatures, 
	 * it will replace them with a new A object with the nonterminals as parameters.
	 * 
	 */
	public abstract Set<Class<?>> getProductions();
	
}